Unlike most modern public-key ciphers, whose security relates to some long-studied mathematical problem that is believed to be difficult to solve (e.g., the factoring or finding discrete logarithms of large integers), the security of most modern symmetric-key pseudo random bit generators (PRBG) do not relate to any widely-studied, hard-to-solve problems. Rather, known PRBGs (e.g., implemented as stream ciphers) are generally designed in an ad hoc fashion to resist known cryptanalytic attacks. As a consequence, the design, analysis and implementation of reliably secure PRBGs is regarded as exceptionally difficult, and is often regarded as more of an art than a science.
The lack of a system and method for developing efficient PRBGs whose reliability and security can be understood or expressed analytically has resulted in the deployment of PRBGs whose security properties have been discovered to be considerably weaker than expected. The discovery of a new weakness in a PRBG undermines security of systems in which it is used, and results in inconvenience and economic loss if the discovered weakness is severe enough to warrant replacing the cipher.
A more serious problem arises if the cipher's user is unaware of a weakness that has been discovered by a third party. This weakness may be exploited without the knowledge of the user to undermine the security of the user's systems for an indeterminate amount of time. This can lead to the unauthorized modification of information (such as the dollar amounts of transfers specified by electronic funds transfer (EFT) messages) and/or the disclosure of confidential and/or sensitive information to unauthorized third parties (e.g., the disclosure of a trade secret.) Such security compromises can cause significant damage to the user and to third parties who rely upon the security of the cipher indirectly (e.g., account holders at a bank that uses EFT protected by the cipher.)
A PRBG with known security properties would eliminate much of the uncertainty surrounding the cipher's security. This would substantially reduce the risk of discovering an unexpected weakness in the cipher, allowing users to rely upon it with more confidence. A cipher with security properties known to be strong would reduce the risk of unauthorized modification and/or compromise of confidential and/or sensitive information. Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
Known PRBGs tend to be conceptually complex. They are often characterized by "magic" constants (i.e., apparently arbitrary constants that have a poorly understood effect on the security of the cipher), irregular structures, and awkward bit-level operations that are inefficient and expensive to implement on computers and/or in telecommunications systems. It is virtually impossible to mathematically comprehend the justifications for many of the various parameters in a typical cipher. These features of known PRBGs can lead a user to improperly implement the cipher in software and/or hardware. Improperly implementing even a single step in some ciphers can render them far less secure.
Cryptanalytic attacks against known PRBGs have often been successfully carried out using known mathematical techniques. For example, the linear feedback shift register algorithm can be compromised by the algebraic manipulation of a few bits of output. A PRBG that cannot be successfully attacked with known mathematical techniques would be more secure than many known PRBGs.
The goal of a PRBG is to provide a cryptographically secure sequence of bits (a "bitstream") that, when applied as a stream cipher, can be added to a cleartext to produce ciphertext and subtracted from the ciphertext to recover cleartext. Cryptographic PRBGs are also used to generate key material and other constants as part of more complex cryptographic protocols.
An ideal cryptographic bit generator is one in which there is no relationship between any one subset of bits in the bitstream and any other subset of bits in the bitstream. That is, the most efficient (compact) representation of the bitstream is simply a complete list of all the bits in the sequence. Such a bit generator is said to be unconditionally secure because knowing any subset of the generated bits does not provide sufficient information to predict the contents of any other subset of generated bits.
In practice, a mathematical function is used to generate a pseudo random stream of bits based upon a small number of bits that comprise the secret state of the generator (e.g., a seed). The most efficient stream generator functions suffer from the disadvantages of complexity and poorly understood security properties, as described above.
It is possible to use a block cipher construction to build a PRBG. One commonly used method is output feedback, in which the previous output of a block cipher is used to provide both the next input to the block cipher and the current stream output. Another known method is counter mode, in which an increasing counter is used as the input to the block cipher and the current stream output is simply the output of the block cipher.
The goal of a block cipher is to provide a reversible transformation on blocks of bits. More precisely, block ciphers are reversible pseudo random permutations that map each of the 2.sup.n possible inputs to a unique n-bit output value. An ideal block cipher would be a completely random permutation, i.e., the only possible representation of the transformation would be a list that completely maps each possible input to an output, and vice versa. This is called a "random function." An example of such a random function for three bit blocks (each of which was selected at random) is as follows:
______________________________________ INPUT 000 001 010 011 100 101 110 111 OUTPUT 010 111 000 110 100 001 011 101 ______________________________________
A truly random function is said to be unconditionally secure because there is no correlation between any one subset of mappings and any other, i.e., the most compact representation of the function is simply a list of all of its mappings of inputs to outputs. Truly random functions can be cumbersome to represent in computer-readable memory for practical block ciphers, and hence are often replaced with pseudo-random functions (PRF) that map inputs to outputs in an apparently random fashion in accordance with a prescribed method. For the most part, only the method (and not the complete listing) of a PRF need be stored in computer-readable memory, resulting in a more efficient implementation of the cipher. The drawback is that a PRF is not unconditionally secure.
A known block cipher is the Feistel construction. H. Feistel, "Cryptography and Computer Privacy." Scientific American, Vol. 228, 1973. The Feistel primitive is shown symbolically as follows:
______________________________________ X = A.vertline.B /*cleartext*/ A = A + f.sub.e B = B + A X = B.vertline.A /*ciphertext*/ ______________________________________
X=A.vertline.B indicates that block of data X has two concatenated halves A and B (".vertline." indicates concatenation). Entry f.sub.e of PRF f is added in this embodiment bitwise modulo-2 (represented by the "+" operator) to A. The result replaces A, which is then added to B modulo-2, resulting in a new value for B. The positions of A and B are switched and concatenated to form a permuted X=B.vertline.A. The primitive can repeated again any number of times using a different PRF each time. Each instance that the primitive is invoked is called a "round." An symbolic representation of a four round Feistel construction is as follows:
______________________________________ X = L.vertline.R /*cleartext*/ R = R + f.sub.1 (L) L = L + f.sub.2 (R) R = R + f.sub.3 (L) L = L + f.sub.4 (R) X = L.vertline.R /*ciphertext*/ ______________________________________
Here, f.sub.1, f.sub.2, f.sub.3 and f.sub.4 are secret pseudo random functions. For a four round, 2n-bit Feistel construction using four n-bit functions a 2n-bit block is divided into a right half R and a left half L in step 1. In step 2, the n-bit left half L of a 2n-bit block X is permuted with a pseudo random function f.sub.1 and added to the n-bit right half R of the block. The result becomes the new right half R. In step 3, the permuted right half R is permuted with another PRF f.sub.2 and added to left half L. The result becomes the new left half L. In step 4, the L is permuted with another PRF f.sub.3 and added to R, the result of which becomes the new R. In step 5, R is permuted with PRF f.sub.4 and added to L, the result of which becomes the new L. In step 6, an enciphered block X=L.vertline.R is obtained.
In order to decipher a block enciphered with the Feistel primitive, the order of the steps of the primitive are reversed and carried out on the enciphered block. This is shown for the Feistel primitive as follows:
______________________________________ X = B.vertline.A /*ciphertext*/ B = B + A A = A + PRF X = A.vertline.B /*cleartext*/ ______________________________________
In order to decipher blocks enciphered with multiple rounds, the rounds should be reversed in reverse order, the most recently used round first. In other words, if the primitive is applied in the sequence r1, r2, . . . , r5, the reverse primitive should be applied in the order r5, r4, . . . , r1 to decipher the block. This is shown as follows:
______________________________________ X = L.vertline.R /*ciphertext*/ L = L + f.sub.4 (R) R = R + f.sub.3 (L) L = L + f.sub.2 (L) R = R + f.sub.1 (L) X = L.vertline.R /*cleartext*/ ______________________________________
Luby and Rackoff showed that if the PRF in an at least four-round Feistel construction are themselves secure, then the resulting permutation is secure. M. Luby and C. Rackoff, "How to Construct Pseudo random Permutations from Pseudo random Functions." SIAM J., Comput., 17 (1988), 373-386. However, Luby and Rackoff provided no information on how to determine if an arbitrary PRF is in fact secure. Thus, a system and method that uses functions known to be secure in an at least four-round Feistel construction will produce permutations that are known to be secure.
The Feistel construction cipher is advantageous because its security (using at least 3 rounds, more preferably at least 4 rounds, and most preferably at least 6 rounds) is closely related to the difficulty of solving the Numerical Matching with Target Sums (NMTS) problem, an NP-Complete problem for which there are no known mathematical techniques to analytically solve. In other words, the only known way to compromise a Feistel construction cipher of three or more rounds is by brute force (e.g., trying all possibilities.)
The security of a stream cipher is partly determined by the period length of the secure bitstream. The bitstream period length is the number of blocks that can be generated before the sequence begins to repeat itself. When the sequence repeats itself, it can be cryptanalytically attacked using known methods. For a block size of 2n there are 2.sup.2 n different blocks, and thus a period length of 2.sup.2 n. The larger the block size, the longer the bitstream period length, and the more secure the PRBG stream cipher. Although increasing the block length increases the security of the bitstream, increasing block length also increases processing time and requires more computer-readable memory, reducing the efficiency of the stream cipher.
A better PRBG stream cipher would possess the advantage of having known security properties such as those disclosed by Luby and Rackoff for the Feistel construction, and be able to be efficiently and practically implemented on computers within the present state of the art.